package prac;

import java.util.*;
import java.util.stream.Collectors;

/**
 题目描述
 在某个项目中有多个任务（用task数组表示）需要你进行处理，其中：
 task[i] = [si, ei]
 你可以在 si ≤ day ≤ ei 中的任意一天处理该任务，请返回你可以处理的最大任务数。
 输入描述
 第一行为任务数量 n
 1 ≤ n ≤ 100000
 后面 n 行表示各个任务的开始时间和终止时间，使用 si，ei 表示
 1 ≤ si ≤ ei ≤ 100000
 输出描述
 输出为一个整数，表示可以处理的最大任务数。
 */
public class Task {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        // 读取并处理第一个输入
        int n = scanner.nextInt();
        Record record;
        List<Record> recordList=new ArrayList<>();
        Map<Integer,List<Record>> nums=new HashMap();
        Map<Integer,Record> recordMap=new HashMap();
        int min=Integer.MAX_VALUE;
        int max=0;
        int start=0;
        int end=0;
        for (int i = 0; i < n; i++) {
            start=scanner.nextInt();
            end=scanner.nextInt();
            record=new Record(start,end);
            recordList.add(record);
            min=min<start?min:start;
            max=min>end?max:end;
            for(int j=start;j<=end;j++){
                if(!nums.containsKey(j)){
                    nums.put(j,new ArrayList<>());
                }
                nums.get(j).add(record);
            }
        }
        for(int i=start;i<=end;i++){
            onlyOne(nums,recordMap);
            if(!nums.containsKey(i)||nums.get(i).size()==0){
                continue;
            }
            List<Record> temps=nums.get(i);
            Collections.sort(temps);
            record=temps.get(0);
            after(nums,recordMap,i,record);
            nums.remove(i);
        }
        System.out.println(recordMap.size());
    }

    /**
     * 选择那些某一天只有一个任务处理的
     * @param nums
     * @param recordMap
     */
    private static void onlyOne(Map<Integer,List<Record>> nums,Map<Integer,Record> recordMap){
        Boolean contine=false;
        Record record=null;

        for(Integer day:nums.keySet()){
            if(nums.get(day).size()==1){
                contine=true;
                record=nums.get(day).get(0);
                after(nums,recordMap,day,record);
                break;
            }
        }
        //如果有数据处理，那可能导致有新的某一天只有1个数据
        if(contine){
            onlyOne(nums,recordMap);
        }

    }

    /**
     * 处理某一天选个某个任务的后续逻辑
     */
    private static void after(Map<Integer,List<Record>> nums,Map<Integer,Record> recordMap,int day,Record record){
        nums.remove(day);
        recordMap.put(day,record);
        for(int j=record.start;j<=record.end;j++){
            if(nums.containsKey(j)){
                nums.get(j).remove(record);
            }
        }
    }



    private static class Record implements Comparable<Record>{
        private  Integer start=0;
        private  Integer end=0;

        public Record(Integer start, Integer end) {
            this.start = start;
            this.end = end;
        }

        public Record() {
        }




        @Override
        public int compareTo(Record o) {
            return  o.start-this.start;
        }

    }
}
